package leetcode.tree;

import java.util.*;

/**
 * @author MaoLin Wang
 * @date 2020/2/1411:19
 */
public class _94中序遍历 {

    public static List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        if (root == null) {
            return list;
        }
        inorder(list, root);
        return list;
    }

    public static void inorder(List<Integer> list, TreeNode root) {
        if (root != null) {
            inorder(list, root.left);
            list.add(root.val);
            inorder(list, root.right);
        }
    }

    /**
     * 莫里斯遍历
     * https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/er-cha-shu-de-zhong-xu-bian-li-by-leetcode-solutio/
     * 一些前置知识：
     * <p>
     * 前驱节点，如果按照中序遍历访问树，访问的结果为ABC，则称A为B的前驱节点，B为C的前驱节点。
     * 前驱节点pre是curr左子树的最右子树（按照中序遍历走一遍就知道了）。
     * 由此可知，前驱节点的右子节点一定为空。
     * 主要思想： 当遍历到当前节点curr时，使用cuur的前驱节点pre
     * <p>
     * 标记当前节点是否访问过
     * 记录回溯到curr的路径（访问完pre以后，就应该访问curr了）
     * 以下为我们访问curr节点需要做的事儿：
     * <p>
     * 访问curr的节点时候，先找其前驱节点pre
     * 找到前驱节点pre以后，我们根据其右指针的值，来判断curr的访问状态：
     * pre的右子节点为空，说明curr第一次访问，其左子树还没有访问，此时我们应该将其指向curr，并访问curr的左子树
     * pre的右子节点指向curr，那么说明这是第二次访问curr了，也就是说其左子树已经访问完了，此时将curr.val加入结果集中
     *
     * @param root
     * @return
     */
    public static List<Integer> inOrderMorris(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        TreeNode current = root;
        TreeNode pre = null;
        while (current != null) {
            if (current.left == null) {
                list.add(current.val);
                current = current.right;
            } else {
                pre = current.left;
                while (pre.right != null) {
                    pre = pre.right;
                }
                if (pre.right == null) {
                    pre.right = current;
                    current = current.left;
                } else {
                    //current 的左子树已经遍历完毕，加入当前节点，开始遍历右子树
                    list.add(current.val);
                    current = current.right;
                }
            }
        }
        return list;
    }

    public static List<Integer> inorderIterate(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        Deque<TreeNode> stack = new LinkedList<>();
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            result.add(root.val);
            root = root.right;
        }
        return result;

    }


    private static void inOrder2(TreeNode root, List<Integer> result) {
        if (root != null) {
            inOrder2(root.left, result);
            result.add(root.val);
            inOrder2(root.right, result);
        }
    }

    public static void main(String[] args) {
        /*
              0
           1    2
              3    4
         */
        TreeNode treeNode = new TreeNode(0);
        treeNode.left = new TreeNode(1);
        treeNode.right = new TreeNode(2);
        treeNode.right.left = new TreeNode(3);
        treeNode.right.right = new TreeNode(4);
        List<Integer> list = inorderIterate(treeNode);
        System.out.println(list);
    }
}
